package com.nl.list;

import com.nl.list.LinkedList.Node;

public class TwoLinkedListFirstCommonNode {

	// 两个链表的第一个公共节点

	public static <T> Node<T> getFirst(Node<T> phead1, Node<T> phead2) {
		if (phead1 == null || phead2 == null) {
			return null;
		}

		int length1 = length(phead1);
		int length2 = length(phead2);
		Node<T> nodeLongList = phead1;
		Node<T> nodeShortList = phead2;
		if (length2 > length1) {
			nodeLongList = phead2;
			nodeShortList = phead1;
		}

		if (length1 != length2) {
			for (int i = 0, len = Math.abs(length1 - length2); i < len; i++) {
				nodeLongList = nodeLongList.next;
			}
		}

		while (nodeLongList != null) {
			if (nodeLongList == nodeShortList) {
				return nodeLongList;
			}
			nodeLongList = nodeLongList.next;
			nodeShortList = nodeShortList.next;
		}
		return null;
	}

	public static <T> int length(Node<T> phead) {
		if (phead == null) {
			return 0;
		}
		Node<T> node = phead;
		int len = 0;
		while (node != null) {
			len++;
			node = node.next;
		}
		return len;
	}

}
